package com.smday.sort;

import java.time.chrono.IsoEra;
import java.util.Arrays;

/**
 * @author Summerday
 */
public class ShellSort {

    public static void main(String[] args) {
        int[] arr = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
        shellSort2(arr);

    }


    public static void shellSortV(int[] arr){

        int count = 0;
        for(int gap = arr.length/2;gap>0;gap/=2){


            for (int i = gap; i < arr.length; i++) {
                //遍历各组中所有的元素,共五组,每组有两个元素
                for (int j = i - gap; j >= 0; j -= gap) {
                    //如果当前元素大于加上步长后的哪个元素,交换
                    if(arr[j]>arr[j+gap]){
                        arr[j] = arr[j]+arr[j+gap];
                        arr[j+gap] = arr[j]-arr[j+gap];
                        arr[j] = arr[j]-arr[j+gap];
                    }

                }


            }
            System.out.printf("第%d轮后: %s\n",++count,Arrays.toString(arr));

        }


    }
    //交换式希尔排序逐步推导
    public static void shellSort(int[] arr) {

        //第一轮

        //第一轮将10个数据分成5组 i--> 3, 5, 4, 6, 0    i-5-->8, 9, 1, 7, 2
        for (int i = 5; i < arr.length; i++) {
            //遍历各组中所有的元素,共五组,每组有两个元素
            for (int j = i - 5; j >= 0; j -= 5) {
                //如果当前元素大于加上步长后的哪个元素,交换
                if(arr[j]>arr[j+5]){
                    arr[j] = arr[j]+arr[j+5];
                    arr[j+5] = arr[j]-arr[j+5];
                    arr[j] = arr[j]-arr[j+5];
                }

            }


        }

        System.out.printf("第1轮后: %s\n",Arrays.toString(arr));
        //第二轮

        //第一轮将十个数据分成5/2 = 2组
        for (int i = 2; i < arr.length; i++) {
            //遍历各组中所有的元素,共五组,每组有两个元素
            for (int j = i - 2; j >= 0; j -= 2) {
                //如果当前元素大于加上步长后的哪个元素,交换
                if(arr[j]>arr[j+2]){
                    arr[j] = arr[j]+arr[j+2];
                    arr[j+2] = arr[j]-arr[j+2];
                    arr[j] = arr[j]-arr[j+2];
                }

            }


        }

        System.out.printf("第2轮后: %s\n",Arrays.toString(arr));

        //第三轮

        //第一轮将十个数据分成2/2 = 1组
        for (int i = 1; i < arr.length; i++) {
            //遍历各组中所有的元素,共五组,每组有两个元素
            for (int j = i - 1; j >= 0; j -= 1) {
                //如果当前元素大于加上步长后的哪个元素,交换
                if(arr[j]>arr[j+1]){
                    arr[j] = arr[j]+arr[j+1];
                    arr[j+1] = arr[j]-arr[j+1];
                    arr[j] = arr[j]-arr[j+1];
                }

            }


        }

        System.out.printf("第3轮后: %s\n",Arrays.toString(arr));

    }

    //移位式希尔排序
    private static void shellSort2(int[] arr){
        int count = 0;
        //增强gap,并逐步的缩小增量
        for(int gap = arr.length/2;gap>0;gap/=2){

            //从第gap个元素开始逐个对其所在的组直接v插入
            for(int i = gap;i<arr.length;i++){

                int insertIndex = i;
                int insertVal = arr[insertIndex];

                if(arr[insertIndex]<arr[insertIndex-gap]){
                    while(insertIndex - gap>=0&&insertVal<arr[insertIndex-gap]){

                        arr[insertIndex] = arr[insertIndex - gap];
                        insertIndex -=gap;

                    }
                    //找到位置
                    arr[insertIndex] = insertVal;
                }


            }
            System.out.printf("第%d轮后: %s\n",++count,Arrays.toString(arr));


        }


    }
}
